﻿using LeetCode100Hot.链表;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//46. 全排列
//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
//47. 全排列 II
//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
//关键区别就是nums可重复，但是结果不可以重复
class Sol47
{


    IList<IList<int>> res = new List<IList<int>>();
    public IList<IList<int>> PermuteUnique(int[] nums)
    {




        IList<int> path = new List<int>();
      
        Array.Sort(nums);
        bool[] used = new bool[nums.Length];
        DFS(nums, path, used);
      

        return res;
    }

    private void DFS2(int[] nums, IList<int> path, bool[] used)//自己写的
    {
       

        if (path.Count == nums.Length)
        {
            res.Add(new List<int>(path));
            return;

        }

        for (int i = 0; i < nums.Length; i++)
        {

            if (used[i])
            {
                continue;
            }
            if (i>0&&nums[i] == nums[i-1] && used[i-1]==true)//used[i-1]==true是为了保护整个树枝的不被剔除,意思是做了树枝去重
            {
                Console.WriteLine(nums[i]);
                continue;
            }
            path.Add(nums[i]);
            used[i] = true;
            DFS2(nums, path,used);
            //回溯
            used[i] = false;
            path.RemoveAt(path.Count - 1);

        }
    }private void DFS(int[] nums, IList<int> path, bool[] used)//代码随想录
    {
       

        if (path.Count == nums.Length)
        {
            res.Add(new List<int>(path));
            return;

        }

        for (int i = 0; i < nums.Length; i++)
        {

           
            if (i>0&&nums[i] == nums[i-1] && used[i-1]==false)//used[i-1]==false，做了树层去重,因为used[i] = false;在循环 做了回溯
            {
                Console.WriteLine(nums[i]);
                continue;
            }
            if (!used[i])
            {
                path.Add(nums[i]);
                used[i] = true;
                DFS(nums, path, used);
                //回溯
                used[i] = false;
                path.RemoveAt(path.Count - 1);
            }
           

        }
    }
}

class Program47
{
    static void Main47(string[] args)
    {

        int[] nums = [1, 1, 2] ;
        Sol47 sol = new();
        IList<IList<int>> res = sol.PermuteUnique(nums);
        for (int i = 0; i < res.Count; i++)
        {

            for (int j = 0; j < res[i].Count; j++)
            {
                Console.Write(res[i][j] + "  ");
            }
            Console.WriteLine();
        }

    }
}
